package com.zp.self.module.level_4_算法练习.算法.位图;

import java.util.HashMap;

/**
 * @author By ZengPeng
 */
public class 力扣_409_最长回文串 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_409_最长回文串().longestPalindrome("abccccdd"));
        System.out.println(new 力扣_409_最长回文串().longestPalindrome("a"));
        System.out.println(new 力扣_409_最长回文串().longestPalindrome("bb"));
        System.out.println(new 力扣_409_最长回文串().longestPalindrome("abcd"));
    }

    /**
     * 题目：给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。
     * 在构造过程中，请注意 区分大小写 。比如 "Aa" 不能当做一个回文字符串。
     *
     * 示例 1:
     * 输入:s = "abccccdd"
     * 输出:7
     * 解释:
     * 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
     *
     * 示例 2:
     * 输入:s = "a"
     * 输入:1
     *
     * 分析：
     *      1.位图记录：字符出现偶数次的+1
     *      2.hashMap记录
     *
     * 边界值 & 注意点：
     *      1.
     **/
    public int longestPalindrome(String s) {
        HashMap<Character,Integer> hashMap = new HashMap<>();
        for (char c : s.toCharArray())
            hashMap.put(c,hashMap.getOrDefault(c,0)+1);
        int sum =0;
        boolean single = false;
        for (Integer value : hashMap.values()) {
            if(!single &&(value&1) ==1) single=true;
            sum+=(value>>1<<1);
        }
        return single?sum+1 :sum;
    }
}
